package com.Oct_ThirtyOne;

/**
 * 481. 神奇字符串
 * 神奇字符串 s 仅由 '1' 和 '2' 组成，并需要遵守下面的规则：
 *
 * 神奇字符串 s 的神奇之处在于，串联字符串中 '1' 和 '2' 的连续出现次数可以生成该字符串。
 * s 的前几个元素是 s = "1221121221221121122……" 。如果将 s 中连续的若干 1 和 2 进行分组，可以得到 "1 22 11 2 1 22 1 22 11 2 11 22 ......" 。每组中 1 或者 2 的出现次数分别是 "1 2 2 1 1 2 1 2 2 1 2 2 ......" 。上面的出现次数正是 s 自身。
 *
 * 给你一个整数 n ，返回在神奇字符串 s 的前 n 个数字中 1 的数目。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/magical-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 2022/10/31 15:38
 */

public class Solution481 {

//    public int magicalString(int n) {
//        if (n<=3) return 1;
//        StringBuilder stringBuilder=new StringBuilder("122");
//        for (int i = 2; stringBuilder.length() < n; ) {
//            for (int j = stringBuilder.charAt(i++)-'0'; j >0 ; j--) {
//                stringBuilder.append("1");
//            }
//            for (int j = stringBuilder.charAt(i++)-'0'; j >0 ; j--) {
//                stringBuilder.append("2");
//            }
//        }
//        int res=0;
//        for (int i = 0; i < stringBuilder.length(); i++) {
//            res+=stringBuilder.charAt(i)=='1'?1:0;
//        }
//        return res;
//    }

    public int magicalString(int n) {
        int[] magic=new int[n];
        magic[0]=1;
        int index=1,count=2,tail=1,ans=1,value=1;
        while (tail<n)
        {
            value^=3;
            while (count-->0&&tail<n)
            {
                magic[tail++]=value;
                if (value==1) ans++;
            }
            count=magic[++index];
        }
        return ans;
    }

    public static void main(String[] args) {
        Solution481 solution481=new Solution481();
        System.out.println(solution481.magicalString(6));
    }

}
